﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TextEditApp.Algorithm
{
    class MinDistance
    {
        /// <summary>
        /// 输入两个字符串，输出一个字符通过增、删、改转化为另一个字符所需的最小次数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        static public int GetMinDis(string a,string b)
        {
            int m = a.Length;
            int n = b.Length;
            int[,] dp = new int[m + 1, n + 1];
            for (int i = 0; i <= m; i++) dp[i, 0] = i;
            for (int i = 0; i <= n; i++) dp[0, i] = i;

            for(int i = 1;i <= m; i++)
            {
                for(int j = 1;j <= n; j++)
                {
                    int[] cand = { dp[i - 1, j] + 1, dp[i, j - 1] + 1, dp[i - 1, j - 1] + Convert.ToInt32(a[i - 1] != b[j - 1]) };
                    dp[i, j] = cand.Max();
                }
            }

            return dp[m, n];
        }
    }
}
